\documentclass[a4paper,12pt]{article}
\usepackage[left=2cm,right=2cm,
    top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\renewcommand{\abstractname}{Аннотация}
\title{}
\date{}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc} 
\usepackage[russian,english]{babel}
\usepackage[pdftex,unicode]{hyperref}
\usepackage{indentfirst} 
\begin{document}
\author{Кретов Алексей\\
Информационный поиск}
\begin{center}
\LARGE{Санкт--Петербургский государственный университет}\\[0.4cm]
\LARGE{Математико--механический факультет}\\[0.4cm]
\textbf{Кафедра информатики}\\[3cm]
\textsc{\LARGE{Информационный поиск}}\\[3cm]
Курсовая работа студента 244 группы\\
Кретова Алексея Константиновича\\[4cm]
\end{center}
\begin{flushleft}
\large{
Научный руководитель\\
к.ф.--м.н., доцент~~~~~~~/Барашев Д.В./\\
Оценка}\\[7cm]           
\end{flushleft}
\begin{center}
                Санкт--Петербург
                         2010
\end{center}
\begin{abstract}
\textbf{Целью данной работы} является написание некой программы --- «поисковика» по Java--коду готовых программ, который должен отвечать запросы списком имен релевантных файлов (имеющих Java природу). Такая программа поможет при прове\-дении модернизации готовых программных продуктов (обновлении функциональнос\-ти, например).
\end{abstract}
\section{Введение}
Для начала поговорим о самом понятии «информационный поиск» или Information retrieval, а точнее дадим ему определение. Итак, информационный поиск --- это поиск материала (обычно документов) с неструктури\-рованной природой (или же слабо структури\-рованной), который удовлетворяет некоторому запросу, из большой коллекции документов (корпус). Материалы, удовлетворяющие запро\-су, называются релевантными, соответствен\-но релевантность --- степень соответствия ре\-зультатов поиска и запроса. Реле\-вант\-ность может определяться по--разному, наверное, наиболее простым примером её определения будет следующий при\-мер: если термин есть в файле (точное совпадение встречается хотя бы один раз), то файл релевантный.

Говоря о поиске, также мы обязательно должны упомянуть об индексировании докумен\-тов. Естествен\-но, простой поиск подстроки, взятой из запроса, в документе корпуса по всему его тексту не будет работать из-за низкой производительности. Разумнее будет определить отображе\-ние \textsc{f : files $\rightarrow$ terms}, сопоставляющее каждому файлу множество терминов, встре\-чающихся в нем, тем самым мы строим примитивный индекс каждого файла. Рассмот\-рим пример индексирования документов, используем булевскую модель поиска, то есть запрос будет представлять собой булевское выражение от искомых терминов с операциями AND, OR и NOT (например, Mama AND myla AND (ramu OR Papu)).
\section{Реализация поисковика}
\subsection{Поиск с помощью матрицы инциденций}
Имеем пять коробок, наполненных фруктами (коробки составляют корпус, фрукты – термины). Построим матрицу инцидентности, столбцы пометим \textbf{ID} документов, а строки терминами, тогда \textbf{A[i][j]} --- элемент будет равен 1, если \textbf{i} термин встречается в документе \textbf{j}, или 0 в противном случае.  Каждому термину соответствует строка из 0 и 1, которая дает полную информацию о его наличии в документах корпуса.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
&box1&box2&box3&box4&box5\\
\hline
Apple &1&0&0&1&0\\
\hline
Orange &0&1&0&0&1\\
\hline
Grapefruit  &0&0&1&1&1\\
\hline
\end{tabular}
\caption{Матрица инцидентности.}
\end{center}
\end{table}

\begin{flushleft}
Запрос:\\
\textsc{Apple OR Orange AND Grapefruit}\\
Запрос после преобразования с учетом построенной матрицы инцидентности:\\
\textsc{10010 OR 01001 AND 00111 = 10011}\\
\end{flushleft}

Из примера мы можем видеть, что работа с матрицей очень проста и реализация не вызовет затруд\-нений, но оборотная сторона простоты --- затраты на хранение матрицы --- выше показана матрица из 15 элементов, а если корпус состоит из 1\textbf{M} файлов и терминов в них 1000? Памяти для хранения $10^9$ элементов памяти вполне может не хватить, для решения этой проблемы перейдем к второму подходу.
\subsection{Инвертированный поиск}
В подавляющем большинстве реальных случаев, если выполнять построение матрицы инцидентности, то бОльшая часть её элементов будет 0, очевидно, что в таком случае правильнее будет хранить для каждого термина \textbf{ID} только тех документов, в которых этот термин появлялся. Тут-то нам и пригодятся обратные индексы. Опять же проиндексируем все документы, но теперь в добавление к этому построим обратное отображение \textsc{g : terms  	$\rightarrow$ files}, с помощью которого сопоставим каждому термину из словаря, построенного на основе документов корпуса, список, показывающий в каких документах слово найдено, каждый элемент этого списка --- запись, содержащая \textbf{ID} документа и называющаяся \textbf{posting}, а сам список --- \textbf{postings--list}. Посмотрим, как будет выглядеть картина примера из первого подхода теперь.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|}
\hline
Apple & box1 box4 \\
\hline
Orange & box2 box5 \\
\hline
Grapefruit & box3 box4 box5 \\
\hline
\end{tabular}
\caption{Postings--list.}
\end{center}
\end{table}

Очевидно, что такая структура будет требовать намного меньше памяти для хранения по сравнению с матрицей, особенно в случаях, когда корпус содержит большое количество документов, но в тоже время функциональность на том же уровне. Заметим, что при индексировании внимание стоит уделять размеру индекса и скорости его построения, ибо это влияет на размеры корпуса, который можно будет обработать. Так же стоит понимать, что в примере показано простое устройство posting, в реальности же, записи могут содержать не только \textbf{ID} (например, еще позицию в документе), а документы в списке могут быть упорядочены по-разному.
	
Теперь же немного конкретики о выполняемой задаче. Реализовывать будем поисковик с запросами без операторов и скобок.  Корпус в нашем случае будет состоять из Java-source файлов, готового проекта, искать в нем необходимо имена классов, их полей и методов. Для индексирования файлов (непосредственного получения нужных терминов) необходимо их распарсить (Parsing), для этого используем Eclipse JDT, индексы будем хранить в памяти. Postings-list будут содержать исключительно имена файлов и более никакой информации, списки останутся не упорядоченными. Сделаем еще несколько замечаний по работе программы. Запрос будет проверяться  на наличие повторений, в итоге после обработки каждое слово будет уникальным. Обработка запроса выполняется с помощью конечного автомата, который имеет три состояния: whitespace, word, end. Каждое состояние является реализацией интерфейса State, имеющего одну единственную функцию eat, которая получает входной символ и возвращает новое состояние. Сложность алгорит\-ма поиска будет $\Theta$(N*M), где N --- количество терминов в соваре, а M --- количество слов в запросе.
\section{Эксперименты}	
\subsection{Описание тестов}
Для тестирования написанной программы смоделируем ситуацию близкую к реальной. Подопытным кроликом будут исходники различных open source проектов. Тестирование будет проходить в три этапа, разделение на которые будет осуществляться в соответствии с размерами корпуса.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|}
\hline
\textbf{Test}&\textbf{Size}\\
\hline
Kitty&1000 файлов \\
\hline
Cat&5000 файлов\\
\hline
Lion&10000 файлов \\
\hline
\end{tabular}
\caption{Размеры корпусов.}
\end{center}
\end{table}

Запросы, участвующие в тесте, будут составлены из терминов словаря для соответствую\-щих исходников таким образом, что ответ программы должен быть непустым. В среднем и большом запросе будет присутствовать как минимум одно слово с очень высокой селектив\-ностью, естественно, что все слова уникальны. Самый маленький же запрос будет составлен исключительно из уникальных терминов с очень высокой селективностью, чтобы нагляднее показать зависимость от размера корпуса. Каждый запрос при тестировании будет произво\-диться десять раз и в таблицу попадет среднее значение по всем тестам, исключая минималь\-ное и максимальное время.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|}
\hline
\textbf{Query}&\textbf{Size}\\
\hline
Small&3 термина\\
\hline
Normal&10 терминов\\
\hline
Huge&25 терминов \\
\hline
\end{tabular}
\caption{Размеры запросов.}
\end{center}
\end{table}
\subsection{Результаты}

Следующая таблица демонстрирует результаты экспериментов, она показывает зависи\-мость времени поиска от размера корпуса (тестирование с маленьким запросом) и длины запроса, а также времени индексирования от размера корпуса. Данные в таблице указаны в секундах.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
&\textbf{Kitty}&\textbf{Cat}&\textbf{Lion}\\
\hline
Index/Invert &6.859&19.955&59.497\\
\hline
Small&0.00296&0.0153&0.0268\\
\hline
Normal &0.0106&0.0268&0.0403\\
\hline
Huge &0.0238&0.0545&0.0977\\
\hline
\end{tabular}
\end{center}
\caption{Результаты.}
\end{table}
\section{Заключение}

В ходе выполнения данной работы был написан простой поисковик, работающий с корпусом из слабоструктурированных файлов, а если точнее, то с Java--source корпусом, программа использует для обработки документов средства Eclipse. ыли проведены экспери\-менты, показывающие зависимость времени работы от размеров корпуса и длины запроса.

Данная работа является лишь введением в информационный поиск. Дальнейшие иссле\-дова\-ния будут касаться поиска кода в готовом проекте по смыслу требуемого расшерения функциональ\-ности и оценки трудоемкости выполнения этого расширения. 

\section{Список литературы}
{[1]}Sun Microsystems, June 25, 2003. JSE Specification, http://java.sun.com/j2se/1.4.2/docs/api/.\\
{[2]}Lars Vogel, 2007-2010. http://www.vogella.de.\\
{[3]}Manning, C. D., Raghavan, P.,  Schütze, H. (2008). Introduction to information retrieval. Cambridge, England: Cambridge University Press.\\
{[4]}Bruce Eckel, 2009, Философия Java, Изд.: Питер.
\end{document}